public class l21 {
    public static void main(String[] args) {
        /* 
        ListNode lista_head = new ListNode();
        ListNode lista_node1 = new ListNode(1);
        ListNode lista_node2 = new ListNode(2);
        ListNode lista_node3 = new ListNode(4, null);
        ListNode listb_head = new ListNode();
        ListNode listb_node1 = new ListNode(1);
        ListNode listb_node2 = new ListNode(3);
        ListNode listb_node3 = new ListNode(4,null);
        lista_head.next = lista_node1;
        lista_node1.next = lista_node2;
        lista_node2.next = lista_node3;

        listb_head.next = listb_node1;
        listb_node1.next = listb_node2;
        listb_node2.next = listb_node3;
        */
        /* 
        ListNode lista_head = new ListNode();
        ListNode lista_node1 = new ListNode(2);
        ListNode listb_head = new ListNode();
        ListNode listb_node1 = new ListNode(1);
        
 
        lista_head.next = lista_node1;
        lista_node1.next = null;
        
        //lista_node1.next = lista_node2;
        //lista_node2.next = lista_node3;

        listb_head.next = listb_node1;
        listb_node1.next = null;
        
        //listb_node1.next = listb_node2;
        //listb_node2.next = listb_node3;
        */

        //// [5], [1, 2, 4]
        ListNode lista_head = new ListNode();
        ListNode lista_node1 = new ListNode(5,null);
        //ListNode lista_node2 = new ListNode(2);
        //ListNode lista_node3 = new ListNode(4, null);
        ListNode listb_head = new ListNode();
        ListNode listb_node1 = new ListNode(1);
        ListNode listb_node2 = new ListNode(2);
        ListNode listb_node3 = new ListNode(4,null);
        lista_head.next = lista_node1;
        //lista_node1.next = lista_node2;
        //lista_node2.next = lista_node3;

        listb_head.next = listb_node1;
        listb_node1.next = listb_node2;
        listb_node2.next = listb_node3;
        
        ////





        

        ////
        ListNode results = new ListNode();
    
        lista_head = lista_node1;
        listb_head = listb_node1;

        results = mergeTwoLists(lista_head, listb_head);
        if (results == null)
            System.out.println("[]");
        while (results != null) {
            System.out.print(results.val+",");
            results = results.next;
        }


    }
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // list1 fixed
        ListNode list1head = list1;
        ListNode list2head = list2;
        ListNode list1Last = list1;
        ListNode list2Last = list2;
        //ListNode list2Next = list2.next;
                
        if(list1 == null && list2 == null)
            return null;
        if (list1 == null && list2 != null)
            return list2;
        if (list2 == null && list1 != null)
            return list1;

        while (list1 != null) {
            
            if (list1!=null)
                System.out.println("list1.val="+list1.val);
            if (list2!=null)
                System.out.println("list2.val="+list2.val);

            if (list2.val < list1.val) {
                list2Last = list2;
                //list2Next = list2.next;
                //list1head = list2head; //switch leading list to list2 due to list2 is smaller than list1
                //list1Last.next = list2;
                while (list2!=null && list2.val < list1.val) {
                    list2Last = list2;
                    //list2Next = list2.next;
                    list2 = list2.next;


                }
                // fix me? comment out
                //list1Last.next = list2Last;
                //System.out.println("smaller:list1Last.val="+list1Last.val);
                list2Last.next = list1;
                System.out.println("smaller:list2Last.val="+list2Last.val);
                // fix 
                list1head = list2head;
            } else { // list2 >= list1
                list1Last = list1;
                while (list1!=null&&list2.val >= list1.val) {
                    list1Last = list1;
                    list1 = list1.next;

                }
                list1Last.next = list2;
                list2Last = list2;
                while (list2!=null && list1!=null &&list2.val < list1.val) {
                    list2Last = list2;
                    list2 = list2.next;
                }
                list2Last.next = list1;
                //bug fix: should also update the list1Last node
                list1Last = list2Last;
                //bug fix: should rewind list1 node to list1Last
                list1 = list1Last;
                System.out.println("greater: List1Last.val:"+list1Last.val);
                System.out.println("greater: List2Last.val:"+list2Last.val);

                System.out.println("greater: List1.val:"+list1.val);
                System.out.println("greater: List2.val:"+list2.val);
                if (list1Last.next != null)
                    System.out.println("greater: List1Last.next.val:"+list1Last.next.val);
                if (list2Last.next != null)
                    System.out.println("greater: List2Last.next.val:"+list2Last.next.val);
                if (list1.next != null)
                    System.out.println("greater: List1.next.val:"+list1.next.val);
                if (list2.next != null )
                    System.out.println("greater: List2.next.val:"+list2.next.val);
                
            
            }

            list1 = list1.next;
        }

        
        return list1head;
    }




}
